/*
 * @Author: Wushiqi
 * @Descripttion: 冒泡排序法
 * @Date: 2021-05-14 10:16:01
 * @LastEditor: Wushiqi
 * @LastEditTime: 2021-05-14 15:12:59
 */
const bubble = document.getElementById('bubble')
const before1 = document.getElementById('before-bubble')
const after1 = document.getElementById('after-bubble')
const quick = document.getElementById('quick')
const before2 = document.getElementById('before-quick')
const after2 = document.getElementById('after-quick')
const insert = document.getElementById('insert')
const before3 = document.getElementById('before-insert')
const after3 = document.getElementById('after-insert')

function createArr(n) {
  let arr = []
  for (let i = 0; i < n; i++) {
    let data = Math.ceil(Math.random()*50)
    if (arr.indexOf(data) !== -1) { // 防止产生重复数据
      data = Math.ceil(Math.random()*50)
      i--
    } else {
      arr.push(data)
    }
  }
  return arr
}

// 冒泡排序
bubble.addEventListener('click', () => {
  const arr = createArr(16)
  before1.innerHTML = '[' + arr.join(',  ') + ']'
  console.time('冒泡排序')
  bubbleSort(arr)
  after1.innerHTML = '[' + arr.join(',  ') + ']'
  console.timeEnd('冒泡排序')
})
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) { // 从后一项开始比较
      const [cur, next] = [arr[i], arr[j]]
      if (cur > next) { // 如果当前项大于后一项，则交换位置
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
}

// 快速排序
// 先拿出一个数，然后挨个比较，比它小的放左边，比它大的放右边，然后递归操作左右两个数组
quick.addEventListener('click', () => {
  const arr = createArr(16)
  before2.innerHTML = '[' + arr.join(',  ') + ']'
  console.time('快速排序')
  const newArr = quickSort(arr)
  after2.innerHTML = '[' + newArr.join(',  ') + ']'
  console.timeEnd('快速排序')
})
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let left = []
  let right = []
  const cur = arr[0]
  for (let i = 1; i < arr.length; i++) {
    // for (let j = arr.length - 1; j >= i; j--) {
    const next = arr[i]
    if (next > cur) {
      right.push(next)
    } else {
      left.push(next)
    }
  }
  const res = quickSort(left).concat([cur], quickSort(right))
  return res
}

// 插入排序
insert.addEventListener('click', () => {
  const arr = createArr(16)
  before3.innerHTML = '[' + arr.join(',  ') + ']'
  console.time('插入排序')
  const newArr = insertSort(arr)
  after3.innerHTML = '[' + newArr.join(',  ') + ']'
  console.timeEnd('插入排序')
})
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const next = arr[i] // 要插入列表的新数据
    let j = i - 1 // 默认已排序的
    while (j >=0 && next < arr[j]) { // 要插入的数据小于已排序的，从后往前扫描已排序的
      // 已排序的往后挪一位
      arr[j + 1] = arr[j]
      j--
    }
    // 要插入的数据大于已排序的，直接在已排序列表后面加上新数据
    arr[j + 1] = next
  }
  return arr
}